home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 02 Useful Techniques / 08 Zarozinski / src / ffllapi / MemberFuncSCurve.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-10-16  |  16.6 KB  |  657 lines
  1. //
  2. // File:    MemberFuncSCurve.cpp
  3. //
  4. // Purpose:    Implementation of the MemberFuncSCurve membership function
  5. //
  6. // Copyright ⌐ 1999-2001 Louder Than A Bomb! Software
  7. //
  8. // This file is part of the FFLL (Free Fuzzy Logic Library) project (http://ffll.sourceforge.net)
  9. // It is released under the BSD license, see http://ffll.sourceforge.net/license.txt for the full text.
  10. //
  11.  
  12. #include "MemberFuncSCurve.h"
  13. #include "MemberFuncSingle.h"
  14. #include "FuzzyModelBase.h"
  15. #include "FuzzyVariableBase.h"
  16.  
  17.  
  18. #ifdef _DEBUG  
  19. #undef THIS_FILE
  20. static char THIS_FILE[]=__FILE__;
  21. #endif
  22.  
  23.  
  24. //
  25. // Function:    MemberFuncSCurve()
  26. // 
  27. // Purpose:        Constructor
  28. //
  29. // Arguments:
  30. //
  31. //        FuzzySetBase* _parent - Set this member function is part of
  32. //
  33. // Returns:
  34. //
  35. //        nothing
  36. //
  37. // Author:    Michael Zarozinski
  38. // Date:    8/99
  39. // 
  40. // Modification History
  41. // Author    Date        Modification
  42. // ------    ----        ------------
  43. //
  44. //
  45. MemberFuncSCurve::MemberFuncSCurve(FuzzySetBase* _parent) : MemberFuncBase(_parent), FFLLBase(_parent)
  46. {
  47.     // create the nodes array
  48.     alloc_nodes( get_node_count() );
  49.  
  50. } // MemberFuncSCurve::MemberFuncSCurve()
  51.  
  52.  
  53.  
  54.  
  55. //
  56. // Function:    ~MemberFuncSCurve()
  57. // 
  58. // Purpose:        Destructor
  59. //
  60. // Arguments:
  61. //
  62. //        none
  63. //
  64. // Returns:
  65. //
  66. //        nothing
  67. //
  68. // Author:    Michael Zarozinski
  69. // Date:    8/99
  70. // 
  71. // Modification History
  72. // Author    Date        Modification
  73. // ------    ----        ------------
  74. //
  75. // 
  76. MemberFuncSCurve::~MemberFuncSCurve() 
  77. {
  78.     // nothing to do, base class(es) handle everything
  79. }
  80.  
  81. //
  82. // Function: set_node()
  83. // 
  84. // Purpose:    This function moves a point to a new position. It performs
  85. //            checks to make sure the nodes are at valid positions (such as
  86. //            not allowing the last point to be BEFORE the mid point.
  87. // 
  88. // Arguments:
  89. //
  90. //        int            idx            -    index of the point to move
  91. //        int            x            -    x position to move to (in variable coords)
  92. //        int            y            -    x position to move to (in variable coords)
  93. //        bool        validate    -    indicates if we should perorm sanity checks (default is true)
  94. //
  95. // Returns:
  96. //
  97. //        void
  98. // 
  99. // Globals:
  100. //
  101. // Author:    Michael Zarozinski    
  102. // Date:    6/21/99
  103. // 
  104. //    Modification History
  105. //    Author        Date        Modification
  106. //    ------        ----        ------------
  107. //     
  108. //
  109. void MemberFuncSCurve::set_node(int idx, int x, int y, bool validate /* = true */)
  110. {
  111.     if (!validate)
  112.         {
  113.         nodes[idx].y = y;
  114.         nodes[idx].x = x;
  115.         return;
  116.         }
  117.  
  118.      // if the node is 1, 2, 4, or 5 the 'y' direction can be changed.
  119.     if (idx == 0 ||  idx == 6)
  120.           y = 0;
  121.  
  122.      // check the first point...
  123.     if (idx == 0)
  124.         {
  125.         // we're dealing with an end point
  126.         if( x > nodes[1].x)
  127.             nodes[idx].x = nodes[1].x;
  128.         else
  129.             nodes[idx].x =  x;
  130.         }
  131.     else if (idx == 6)
  132.         { 
  133.         // we're dealing with the last point
  134.         if ( x < nodes[5].x)
  135.             nodes[idx].x = nodes[5].x;
  136.         else
  137.             nodes[idx].x =  x;
  138.         }
  139.     else
  140.         {
  141.         if ( x < nodes[idx - 1].x)
  142.             nodes[idx].x = nodes[idx - 1].x;
  143.         else if ( x > nodes[idx + 1].x)
  144.             nodes[idx].x = nodes[idx + 1].x;
  145.         else
  146.             nodes[idx].x = x;
  147.  
  148.          nodes[idx].y = y;
  149.         }
  150.         
  151. } // end MemberFuncSCurve::set_node()
  152.  
  153.  
  154. //
  155. // Function:    init_nodes()
  156. // 
  157. // Purpose:        Initialized all the nodes to reasonable values depending on the 
  158. //                mid-point and width passed in.
  159. //
  160. // Arguments:
  161. //
  162. //            int        mid_pt_x    -    mid point of the member func
  163. //            int        width        -    how wide this set is
  164. // 
  165. // Returns:
  166. //
  167. //            none
  168. //
  169. // Author:    Michael Zarozinski
  170. // Date:    6/21/99
  171. // 
  172. // Modification History
  173. // Author    Date        Modification
  174. // ------    ----        ------------
  175. //
  176. //
  177.  
  178. void MemberFuncSCurve::init_nodes(int mid_pt_x, int term_width)
  179. {
  180.     int i;  // counter
  181.  
  182.     // set start point
  183.     nodes[0].x = mid_pt_x - term_width/2;
  184.      nodes[0].y = 0;
  185.  
  186.     // set mid point
  187.     nodes[3].x = mid_pt_x;
  188.     nodes[3].y = FuzzyVariableBase::get_dom_array_max_idx();
  189.  
  190.     // set end point
  191.     nodes[6].x = nodes[0].x + term_width;
  192.     nodes[6].y = 0;
  193.  
  194.     // now use common code to calc the other points...
  195.  
  196.     init_nodes(nodes[0], nodes[3], nodes[6]);
  197.  
  198.     // the only sanity check we'll do is to make sure we don't go "over" the midpoint
  199.  
  200.     for (i = 0; i < 3; i++)
  201.         {
  202.         if (nodes[i].x > mid_pt_x)
  203.             nodes[i].x = mid_pt_x;
  204.         }
  205.     for (i = 4; i < 7; i++)
  206.         {
  207.         if (nodes[i].x < mid_pt_x)
  208.             nodes[i].x = mid_pt_x;
  209.         }
  210.  
  211.     calc(); // for this curve we must calc the curve. 
  212.  
  213. } // end MemberFuncSCurve::init_nodes()
  214.  
  215.  
  216.  
  217. //
  218. // Function:    init_nodes()
  219. // 
  220. // Purpose:        Initialized the nodes that can have their 'y' value changed
  221. //                based on the position of the start, mid, and end points
  222. //
  223. // Arguments:
  224. //
  225. //            NodePoint        start_pt    -    start point for the curve
  226. //            NodePoint        mid_pt        -    mid point for the curve
  227. //            NodePoint        end_pt        -    end point for the curve
  228. // 
  229. // Returns:
  230. //
  231. //            none
  232. //
  233. // Author:    Michael Zarozinski
  234. // Date:    6/21/99
  235. // 
  236. // Modification History
  237. // Author    Date        Modification
  238. // ------    ----        ------------
  239. //
  240. //
  241. void MemberFuncSCurve::init_nodes(NodePoint start_pt, NodePoint mid_pt, NodePoint end_pt)
  242. {
  243.      int width = end_pt.x - start_pt.x;
  244.  
  245.     // we can't use set_node cuz it expects all the nodes to be filled in when it
  246.     // performs validations and we don't have them set yet
  247.     nodes[0] = start_pt;
  248.     nodes[3] = mid_pt;
  249.     nodes[6] = end_pt;
  250.  
  251.     int quarter = FuzzyVariableBase::get_dom_array_count() / 4;
  252.  
  253.     // set 'y' values...
  254.     nodes[5].y = nodes[1].y = quarter; // 25% of max
  255.     nodes[2].y = nodes[4].y = quarter * 3; // 75% of max
  256.  
  257.     // if the anchors line up - we're dealing with a ramp... treat that special
  258.     if (start_pt.x == mid_pt.x)
  259.         {
  260.         // left ramp
  261.           nodes[1].x = nodes[2].x = nodes[3].x;
  262.          nodes[4].x = nodes[6].x - width/4;
  263.         nodes[5].x = nodes[6].x - width/8;
  264.         }
  265.     else if (nodes[3].x == nodes[6].x)
  266.         {
  267.         // right ramp
  268.          nodes[5].x = nodes[4].x;
  269.         nodes[1].x = nodes[0].x + width/8; // use a slight offset so they're not on top of each other
  270.         nodes[2].x = nodes[0].x + width/4;
  271.         }
  272.     else 
  273.         {
  274.          nodes[1].x = nodes[0].x + width/8; // use a slight offset so they're not on top of each other
  275.         nodes[2].x = nodes[0].x + width/4;
  276.  
  277.          nodes[4].x = nodes[6].x - width/4;
  278.         nodes[5].x = nodes[6].x - width/8;
  279.         }
  280.  
  281. }; // end MemberFuncSCurve::init_nodes()
  282.   
  283. //
  284. // Function:    calc()
  285. // 
  286. // Purpose:        Virtual function that calculates the 'y' points for this curve
  287. //                 and fills in the values[] array.
  288. //
  289. // Arguments:
  290. //
  291. //        none
  292. //
  293. // Returns:
  294. //
  295. //        void
  296. //
  297. // Author:    Michael Zarozinski
  298. // Date:    5/99
  299. // 
  300. // Modification History
  301. // Author    Date        Modification
  302. // ------    ----        ------------
  303. //
  304. // 
  305. void MemberFuncSCurve::calc()
  306. {
  307.      // clear the values
  308.     clear_values();
  309.   
  310.     // we could use a for loop but this will be faster...
  311.     calc_curve_values(nodes[0], nodes[0], nodes[1], nodes[2]);
  312.     calc_curve_values(nodes[0], nodes[1], nodes[2], nodes[3]);
  313.     calc_curve_values(nodes[1], nodes[2], nodes[3], nodes[4]);
  314.     calc_curve_values(nodes[2], nodes[3], nodes[4], nodes[5]);
  315.     calc_curve_values(nodes[3], nodes[4], nodes[5], nodes[6]);
  316.     calc_curve_values(nodes[4], nodes[5], nodes[6], nodes[6]);
  317.  
  318. } // end MemberFuncSCurve::calc()
  319.  
  320. //
  321. // Function:    calc_curve_values()
  322. // 
  323. // Purpose:        This function that calculates the 'y' points for the segment
  324. //                of the curve between the points (p2 and p3) passed in. It uses
  325. //                the Catmull-Rom Splines algorithm (see code for specifics)
  326. //
  327. // Arguments:
  328. //
  329. //        NodePoint& p1 - node on curve BEFORE the starting node to calc the points for
  330. //        NodePoint& p2 - starting node to calc the points for
  331. //        NodePoint& p3 - end node to calc the points for
  332. //        NodePoint& p4 - node on curve AFTER the starting node to calc the points for
  333. //
  334. // Returns:
  335. //
  336. //        void
  337. //
  338. // Author:    Michael Zarozinski
  339. // Date:    5/99
  340. // 
  341. // Modification History
  342. // Author    Date        Modification
  343. // ------    ----        ------------
  344. //
  345. //   
  346.  
  347. void MemberFuncSCurve::calc_curve_values(NodePoint& p1, NodePoint& p2, NodePoint& p3, NodePoint& p4)
  348. {
  349.     // do some up-front checks to see if we NEED to calc
  350.  
  351.     if ((p3.x == p2.x) && (p3.y < p2.y))
  352.         return;
  353.  
  354.     // This code uses the Catmull-Rom Splines algorithm. p0,p1,p2,p3 are points along
  355.     // the curve, however that the curve drawn actually only passes through points p2 and p3.
  356.     // For values of t between 0 and 1 the curve passes through P2 at t=0 and it passes 
  357.     // through P3 at t=1
  358.     //
  359.     //
  360.     //   q(t) = 0.5 * [ t^3 t^2 t 1 ] * [ -1  3 -3  1 ] * [ p1 ]
  361.     //                                  [  2 -5  4 -1 ]   [ p2 ]
  362.     //                                  [ -1  0  1  0 ]   [ p3 ]
  363.     //                                  [  0  2  0  0 ]   [ p4 ]
  364.     //                                
  365.     //    This becomes : 
  366.     //
  367.     //  q(t) = 0.5 * ((-p1 + 3*p2 -3*p3 + p4)*t*t*t
  368.     //               + (2*p1 -5*p2 + 4*p3 - p4)*t*t
  369.     //               + (-p1+p3)*t
  370.     //               + 2*p2)
  371.     //
  372.     //  OR
  373.     //
  374.     //    q(t) = 0.5 * (a*t^3 + b*t^2 + c*t)
  375.     //
  376.     // Which we can use to find 'x' and 'y' values using the following equations:
  377.     //
  378.     // Eq 1: x = 0.5 * (ax*t^3 + bx*t^2 + cx*t + dx) 
  379.     // Eq 2: y = 0.5 * (ay*t^3 + by*t^2 + cy*t + dy) 
  380.     //
  381.  
  382.      double x, y;    // calculated values
  383.  
  384.     double ax, bx, cx, dx;    // constants
  385.     double ay, by, cy, dy;    // constants
  386.  
  387.     // calc constants up front...
  388.     ax = .5 * (-p1.x + 3*p2.x -3*p3.x + p4.x);
  389.     bx = .5 *(2*p1.x -5*p2.x + 4*p3.x - p4.x);
  390.     cx = .5 *(-p1.x+p3.x);
  391.     dx = p2.x;
  392.  
  393.     ay = .5 *(-p1.y + 3*p2.y -3*p3.y + p4.y);
  394.     by = .5 *(2*p1.y -5*p2.y + 4*p3.y - p4.y);
  395.     cy = .5 *(-p1.y+p3.y);
  396.     dy = p2.y;
  397.  
  398.      int current_idx = p2.x; // current index into values[] array we're calculate the 'y' for
  399.     int next_idx;            // next index in values[] we'll calculate
  400.     float t2;                // calculated t^2 
  401.     bool repeat = false;    // boolean to indicate if we've found the 'y' value
  402.  
  403.     // the curve goes through p2 at t=0 so plugging t=0 into Eq 2 above
  404.     // leaves us with just dy which is p2.y. 
  405.  
  406.     set_value(current_idx, static_cast<DOMType>(p2.y)); // explicit cast to get over ambiguity
  407.  
  408.     // increment current index by one...
  409.     current_idx++;
  410.  
  411.     // calculating the 'y' values is not as simple as having a function that we can
  412.     // plug an 'x' value in for and get the 'y'. 
  413.     // I've tried MANY algorithms (including some from _Numerical Recipes in 'C'_
  414.     // (http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html) 
  415.     // which gave us the ability to provide an 'x' value and get the 'y' 
  416.     // but it's way too "wild" a curve, small movement make for large changes. 
  417.     //
  418.      // We want to have a 'y' value for each 'x' value in the values[] array, so we
  419.     // need to play with the size of the steps we're taking as we go from t=0 to t=1.
  420.      // For example we may get values such as:
  421.     //
  422.     // x = 8.2 for t = 0.003
  423.     // x = 8.8 for t = 0.004
  424.     // x = 9.1 for t = 0.005
  425.     // x = 9.5 for t = 0.006
  426.     //
  427.     // If we're dealing with index 9 in the values[] array we'll use t = 0.005
  428.     // because it's the first value of 't' we found greater than the index we're dealing with
  429.     // We then calculate the 'y' value for that so values[9] = y(0.005) (where y(t) is
  430.     // Eq 2 above).
  431.     //
  432.     // If the distance between p2 and p3 is large, it's very possible to skip 'x' values.
  433.     // For example we may get:
  434.     // x = 8.9 for t = 0.003
  435.     // x = 10.1 for t = 0.004
  436.     // x = 10.9 for t = 0.005
  437.     // x = 11.6 for t = 0.006
  438.     //
  439.     // there's no value we can use for x = 9, so we need to go back and use a smaller
  440.     // step. We go back in "time" by decrementing 't' by the initial step and use a 
  441.     // smaller step, so we may use a step of 0.005 and get:
  442.     // x = 8.9 for t = 0.003
  443.     // x = 9.5 for t = 0.0035
  444.     // x = 10.1 for t = 0.004
  445.     // x = 11.2 for t = 0.0045
  446.     //
  447.     // So we can set values[9] = y(0.0035) (again, using Eq 2 above)
  448.  
  449.      // start with a large step of 0.01
  450.  
  451.      float step = .01f;
  452.  
  453.     // NOTE: we don't step in the 'for' statment cuz we're incrementing it below
  454.     for(double t= 0; t <= 1; /* t+=step,*/ current_idx++)
  455.         { 
  456.         // calc the next index so we know if we've gone past the current 'x' we're dealing with
  457.         next_idx = current_idx + 1;
  458.   
  459.         do    // while(repeat)
  460.             { 
  461.             repeat = false;
  462.  
  463.              do // while (x < current_idx && t <= 1)
  464.                 {
  465.                   t += step; // increment 't' by the step value
  466.                 
  467.                 // calculate t^2
  468.                  t2 = t*t;
  469.  
  470.                 // calculate the 'x' value for this value of 't'
  471.                    x = ax*t*t2 + bx*t2 + cx*t + dx; 
  472.     
  473.                 // while we're still within this 'x' value, keep steping
  474.                 // so we can get the higest value of 't' for this 'x'
  475.  
  476.                 } while (x < current_idx && t <= 1);
  477.  
  478.             // When we get here, the 'x' value is >= the current index we're 
  479.             // concerned with. 
  480.             // if (x > current_idx) *AND* (x > next_idx) then we didn't find a value
  481.             // for the current_idx, we'll try a smaller step and progrssively ratchet
  482.             // down the step until we hit all the 'x' values.  
  483.  
  484.              if (x > next_idx )
  485.                 {
  486.                 // set repeat so we go back to the outter 'do-while' loop
  487.                  repeat = true;
  488.  
  489.                 // step "back in time" by the step we used
  490.                  t -= step;
  491.  
  492.                 // decrease the step
  493.                 if (step > .001f)
  494.                      step -= .001f; // a smallER step
  495.                 else
  496.                     step -= .0005f; // a very small step
  497.  
  498.                 assert(step > 0);
  499.  
  500.                 } // end if x > next_idx 
  501.     
  502.         } while (repeat);
  503.  
  504.     // we found a value for current_idx at time 't', now get the 'y' value
  505.     // for that 't' value
  506.  
  507.        y= (ay*t*t2 + by*t2 + cy*t  + dy);
  508.  
  509.      if (y < 0)
  510.          y = 0.0;
  511.      if (y >= FuzzyVariableBase::get_dom_array_count())
  512.          y = FuzzyVariableBase::get_dom_array_max_idx();
  513.  
  514.      if (current_idx >= FuzzyVariableBase::get_x_array_count())
  515.          return; // saftey
  516.  
  517.        set_value(current_idx, static_cast<DOMType>(y)); // explicit cast to get over ambiguity
  518.  
  519.     } // end for 't' loop
  520.  
  521. } // end MemberFuncSCurve::calc_curve_values()
  522.  
  523.  
  524. //
  525. // Function:    set_ramp()
  526. // 
  527. // Purpose:        Virtual function that sets the nodes appropriately
  528. //                depending on the type of ramp (or no ramp) that we want.
  529. //
  530. // Arguments:
  531. //
  532. //        int left_right_ind        -    indicates if we're making a left (1) or right (0) ramp
  533. //        int hi_lo_ind            -    indicates if we're creating (1) or removing (0) ramp
  534. //
  535. // Returns:
  536. //
  537. //        void
  538. //
  539. // Author:    Michael Zarozinski
  540. // Date:    9/99
  541. // 
  542. // Modification History
  543. // Author    Date        Modification
  544. // ------    ----        ------------
  545. //
  546. //
  547. void  MemberFuncSCurve::set_ramp(int hi_lo_ind, int left_right_ind)
  548. {
  549.     // init the curve so we have a starting point...
  550.  
  551.     nodes[3].x = nodes[0].x + (nodes[6].x - nodes[0].x)/2;
  552.     init_nodes(nodes[0], nodes[3], nodes[6]);
  553.  
  554.     // figure out which side we're changing
  555.     if (hi_lo_ind == 0)
  556.         {
  557.         // set the anchor then fit the handles
  558.         nodes[3].x = nodes[0].x + (nodes[6].x - nodes[0].x)/2;
  559.         }
  560.     else
  561.         {
  562.          if (left_right_ind)
  563.             {
  564.             // make the left the ramp
  565.             nodes[0].x = nodes[1].x = nodes[2].x = nodes[3].x = 0;
  566.             }
  567.         else
  568.             {
  569.             // make the right the ramp
  570.             nodes[3].x = nodes[4].x = nodes[5].x = nodes[6].x   =  FuzzyVariableBase::get_x_array_max_idx();
  571.             }
  572.         } // end if making hi ramp
  573.  
  574.     init_nodes(nodes[0], nodes[3], nodes[6]);
  575.  
  576.     // call the ancestor to deal with common code...
  577.     MemberFuncBase::set_ramp(hi_lo_ind, left_right_ind);
  578.  
  579. } // end MemberFuncSCurve::set_ramp()
  580.  
  581. //
  582. // Function:    expand()
  583. // 
  584. // Purpose:        Uniformly expands this member func around it's center
  585. //
  586. // Arguments:
  587. //
  588. //        int x_delta - how much to expand the member func by        
  589. //
  590. // Returns:
  591. //
  592. //        void
  593. //
  594. // Author:    Michael Zarozinski
  595. // Date:    9/99
  596. // 
  597. // Modification History
  598. // Author    Date        Modification
  599. // ------    ----        ------------
  600. //
  601. // 
  602. void MemberFuncSCurve::expand(int x_delta )
  603. {
  604.     // call init-nodes rather than move nodes to make it look better...
  605.     init_nodes(nodes[3].x, (nodes[6].x - nodes[0].x) + abs(x_delta));
  606.  
  607. } // end MemberFuncSCurve::expand()
  608.  
  609.  
  610. //
  611. // Function:    shrink()
  612. // 
  613. // Purpose:        Uniformly shrinks this member func around it's center
  614. //
  615. // Arguments:
  616. //
  617. //        int x_delta - how much to shrink the member func by        
  618. //
  619. // Returns:
  620. //
  621. //        void
  622. //
  623. // Author:    Michael Zarozinski
  624. // Date:    9/99
  625. // 
  626. // Modification History
  627. // Author    Date        Modification
  628. // ------    ----        ------------
  629. //
  630. //
  631. void MemberFuncSCurve::shrink(int x_delta )
  632. {
  633.      // call init-nodes rather than move nodes to make it look better...
  634.     init_nodes(nodes[3].x, (nodes[6].x - nodes[0].x) - abs(x_delta));
  635.  
  636. } // end MemberFuncSCurve::shrink()
  637.  
  638. /////////////////////////////////////////////////////////////////////
  639. ////////// Trivial Functions That Don't Require Headers /////////////
  640. /////////////////////////////////////////////////////////////////////
  641.  
  642.  
  643. int MemberFuncSCurve::get_center_x(void) const 
  644. {
  645.     // the "mid" x is sepecific to the shape... the start/end x funcs
  646.     // are in the ancestor
  647.  
  648.     return nodes[3].x;
  649. };
  650. int MemberFuncSCurve::get_node_count() const 
  651. { 
  652.     return 7; 
  653. };
  654. int MemberFuncSCurve::get_func_type() const 
  655. {
  656.     return MemberFuncBase::S_CURVE;
  657. };